package nachos.threads;

import nachos.machine.*;

import java.util.LinkedList;
import java.util.Iterator;

/**
 * A round-robin scheduler tracks waiting threads in FIFO queues, implemented
 * with linked lists. When a thread begins waiting for access, it is appended to
 * the end of a list. The next thread to receive access is always the first
 * thread in the list. This causes access to be given on a first-come
 * first-serve basis.
 */
public class RoundRobinScheduler extends Scheduler {
	/**
	 * Allocate a new round-robin scheduler.
	 */
	public RoundRobinScheduler() {
	}

	/**
	 * Allocate a new FIFO thread queue.
	 * 
	 * @param transferPriority
	 *            ignored. Round robin schedulers have no priority.
	 * @return a new FIFO thread queue.
	 */
	public ThreadQueue newThreadQueue(boolean transferPriority) {
		return new FifoQueue();
	}

	private class FifoQueue extends ThreadQueue {
		/**
		 * Add a thread to the end of the wait queue.
		 * 
		 * @param thread
		 *            the thread to append to the queue.
		 */
		public void waitForAccess(KThread thread) {
			Lib.assertTrue(Machine.interrupt().disabled());

			waitQueue.add(thread);
		}

		/**
		 * Remove a thread from the beginning of the queue.
		 * 
		 * @return the first thread on the queue, or <tt>null</tt> if the queue
		 *         is empty.
		 */
		public KThread nextThread() {
			Lib.assertTrue(Machine.interrupt().disabled());

			if (waitQueue.isEmpty())
				return null;

			return (KThread) waitQueue.removeFirst();
		}

		/**
		 * The specified thread has received exclusive access, without using
		 * <tt>waitForAccess()</tt> or <tt>nextThread()</tt>. Assert that no
		 * threads are waiting for access.
		 */
		public void acquire(KThread thread) {
			Lib.assertTrue(Machine.interrupt().disabled());

			Lib.assertTrue(waitQueue.isEmpty());
		}

		/**
		 * Print out the contents of the queue.
		 */
		public void print() {
			Lib.assertTrue(Machine.interrupt().disabled());

			for (Iterator<KThread> i = waitQueue.iterator(); i.hasNext();)
				System.out.print(i.next() + " ");
		}

		private LinkedList<KThread> waitQueue = new LinkedList<KThread>();
	}
}
